package graph;

/**
 * 城市之间的最短距离:
 * 求解城市之间的最短距离是也给非常实际的问题，其大意如下:
 * 某个地区有n个城市，如何选择一条路线使各个城市之间的总距离最短?
 * 最短距离算法：
 * 某个地区的n个城市构成一个交通图:
 * 每个城市代表一个图中的一个顶点。
 * 两个顶点之间的边就是两个城市之间的路径，边的权值代表了城市之间的距离。
 * 这样，求解各个城市之间的最短总距离问题就归结为该图的最小生成树问题。
 *
 * 然后来看一下什么是生成树和最小生成树
 * 如果满足下列条件则称为原图的一个生成树:
 * 子图的顶点和原图完全相同.
 * 子图的分是原图的子集，这一个部分边刚好将图中所有顶点连通。
 * 子图中的边不构成回路。
 *
 * 理论上可以证明，对于有n个顶点的连通图，其生成树有且只有n-1条边，如果边数少于此数就不可能
 * 将各顶点连通，如果边接边的数量多于n-1,则必须要产生回路.
 *
 *
 * 在图论中求解最小生成树，我们可以采用如下算法:
 * (1)将图中所有顶点的集合记为V，最小生成树中的顶点集合为U。初始时，V中包含
 * 所有顶点，而U为空集。
 * (2)首先从V集合中取出一个顶点(设为V0），将其加入到集合U中.
 * (3)从V0的邻接点中选择点Vn,使(V0,Vn)边的权值最小，得到最小生成树中的一条边
 * 将Vn点加入集合U。
 * (4)接着从V-U结合中再选出一个V0、Vn邻接的顶点，找出权值最小的一条边，得到最小生成树的另一条边，
 * 将该顶点加入集合U。
 * (5)按上述步骤不断重复，最后便可以得到该图的最小生成树。
 * 最小生成树
 */
public class MiniDistance {
    static final int MAX_VALUE = 65535;//最大值
    static final int USERD = 0;//已选用顶点
    static final int NOL = -1; //非邻接顶点
    public static void main(String[] args){
        GraphMatrix graphMatrix =  new GraphMatrix();
        graphMatrix.gType = 0;
        graphMatrix.vertextNum = 5;
        graphMatrix.edgeNum = 5;

        for(int i=0;i<graphMatrix.edgeWeight.length;i++){
            for(int j=0;j<graphMatrix.edgeWeight[i].length;j++){
                graphMatrix.edgeWeight[i][j] = (int)(Math.random()*10);
            }
        }
        printGraph(graphMatrix);
    }
    public static class GraphMatrix{
        static final int MAX_NUM = 20;  //图中的最大顶点数
        char[] vertex = new char[MAX_NUM]; //保存顶点信息(序号或字母）
        int gType;         //图的类型(0:无向图，1:有向图)
        int vertextNum;      //顶点的数量
        int edgeNum;            //边的数量
        int[][] edgeWeight = new int[MAX_NUM][MAX_NUM]; //保存边的权
        int[] isTrav = new int[MAX_NUM];   //遍历标志
    }
    public static void printGraph(GraphMatrix graphMatix){
        int k,min;
        int[] weight = new int[GraphMatrix.MAX_NUM];  //权值
        char[] vTempx = new char[GraphMatrix.MAX_NUM];  //临时点信息
        int sum = 0;
        for(int i=0;i<graphMatix.vertextNum;i++){ //保存邻接矩阵中的一行数据
            weight[i] = graphMatix.edgeWeight[0][i];
            if(weight[i]==MAX_VALUE){
                vTempx[i] = (char)NOL;
            }else{
                vTempx[i]=graphMatix.vertex[0]; //邻接点
            }
        }
        vTempx[0] = USERD;  //选用
        weight[0] = MAX_VALUE;
        for(int i=0;i<graphMatix.vertextNum;i++){
            min = weight[0];    //最小权值
            k = i;
            for(int j=1;j<graphMatix.vertextNum;j++){
                if(weight[j]<min&&vTempx[j]>0){ //找到具有更小权值的未使用边
                    min = weight[j]; //保存权值
                    k = j; //保存邻接点序号
                }
            }
            sum += min;   //权值累加
            System.out.printf("%c,%c",vTempx[k],graphMatix.vertex[k]); //输出生成树的一条边
            vTempx[k] = USERD;     //选用
            weight[k] = MAX_VALUE;
            for(int j=0;j<graphMatix.vertextNum;j++) {//重新选择最小边
                if(graphMatix.edgeWeight[k][j]<weight[j] && vTempx[j]!=0){
                    weight[j]=graphMatix.edgeWeight[k][j];//权值
                    vTempx[j]=graphMatix.vertex[k];
                }
            }
        }
        System.out.printf("\n最小生成树的总权值为:%d\n",sum);

    }

}
